#include "lib/global.h"
#include "lib/memctrl.h"
#include "memory/bitmap.h"

void InitBitmap(bitmap* dstBitmap, uint32_t size, ptr_t bits)
{
    dstBitmap->bits = bits;
    dstBitmap->size = size;
    memset_S(bits, 0, size);
    return ;
}

void ClearBits(bitmap* dstBitmap, uint32_t blockstart, uint32_t blocksize)
{
    uint32_t blockStartWord = blockstart / 8;
    uint32_t blockEndWord = (blockstart + blocksize) / 8;
    //如果在同一个字节内
    if(blockEndWord == blockStartWord){
        PTR_R(dstBitmap->bits + blockStartWord) &= ~BitVectorShl(0xff, blockstart % 8, (blockstart + blocksize - 1) % 8);
        return;
    }
    //前面一字节的最后几位置为0
    PTR_R(dstBitmap->bits + blockStartWord) &= ~(0xff << (blockstart % 8));
    //中间部分整体置为0
    memset_S(dstBitmap->bits + blockStartWord + 1, 0, blockEndWord - blockStartWord - 1); 
    //最后一字节的最前几位置为0.（整除情况同样成立）
    PTR_R(dstBitmap->bits + blockEndWord) &= BitVectorShl(0xff, (blockstart + blocksize) % 8, 7);
    return ;
}

void SetBits(bitmap* dstBitmap, uint32_t blockstart, uint32_t blocksize)
{
    uint32_t blockStartWord = blockstart / 8;
    uint32_t blockEndWord = (blockstart + blocksize) / 8;
    //如果在同一个字节内
    if(blockEndWord == blockStartWord){
        PTR_R(dstBitmap->bits + blockStartWord) |= BitVectorShl(0xff, blockstart % 8, (blockstart + blocksize - 1) % 8);
        return;
    }
    //前面一字节的最后几位置为1
    PTR_R(dstBitmap->bits + blockStartWord) |= (0xff << (blockstart % 8));
    //中间部分整体置为1
    memset_S(dstBitmap->bits + blockStartWord + 1, 0xff, blockEndWord - blockStartWord - 1); 
    //最后一字节的最前几位置为1
    PTR_R(dstBitmap->bits + blockEndWord) |= ~BitVectorShl(0xff, (blockstart + blocksize) % 8, 7);
    return ;
}

uint32_t GetBitsBlock(bitmap* dstBitmap, uint32_t blockSize)
{
    //当前的指针
    ptr_t bitsPtr = dstBitmap->bits;
    //结束的指针
    ptr_t endPtr = dstBitmap->bits + dstBitmap->size;
    //当前连续的位数
    uint32_t keepCnt;
    uint32_t tempCnt;
    //返回的结果
    uint32_t retIndex;
    uint32_t tempIndex;
    //当前字的内容
    uint32_t content;
    uint32_t tmp;
    while(bitsPtr < endPtr)
    {
        //跳过所有的全部被分配的字节
        if(PTR_R(bitsPtr) == 0xff){
            bitsPtr++;
            continue;
        }
        //在当前字里寻找连续最多的位, 起始位下标和长度分别保存在retIndex和keepCnt里面
        content = PTR_R(bitsPtr);
        tempIndex = 0;
        keepCnt = 0;
        tempCnt = 0;
        // 从头开始找，一旦找够了直接退出
        for(tmp = 0; tmp < 8 && tempCnt < blockSize; tmp++){
            if(GetBitShl(content, tmp) == 0){
                tempCnt++;
            }
            else{
                if(tempCnt > keepCnt){
                    keepCnt = tempCnt;
                    retIndex = tempIndex;
                }
                tempCnt = 0;
                tempIndex = tmp + 1;
            }
        }
        if(tempCnt > keepCnt){
            keepCnt = tempCnt;
            retIndex = tempIndex;
        }
        //如果一个字节的内容就够了
        if(keepCnt >= blockSize){
            retIndex = 8 * (bitsPtr - dstBitmap->bits) + retIndex; 
            SetBits(dstBitmap, retIndex, blockSize);
            return retIndex;
        }
        //如果还不够, 先记录下最高位的0的个数
        keepCnt = 0;
         while((content & 0x80) == 0 && keepCnt < 8){
            keepCnt++;
            content <<= 1;
        }
        retIndex = 8 * (bitsPtr - dstBitmap->bits) + 8 - keepCnt;
        // 考察下一块，当差的块数超过整个字节时
        bitsPtr++;
        while(blockSize - keepCnt >= 8 && bitsPtr < endPtr){
            if(PTR_R(bitsPtr) == 0){
                keepCnt += 8;
            }
            else{
                 //肯定不够了, 通过两次跳转脱离出去重新寻找
                break;
            }
            bitsPtr++;
        }
        if(blockSize - keepCnt >= 8){
            continue;
        }
        // 考察最后一块是否足够分配
        //如果够
        if(BitVector(PTR_R(bitsPtr), 0, blockSize - keepCnt - 1) == 0){
            SetBits(dstBitmap, retIndex, blockSize);
            return retIndex;
        }
        //如果不够，进入下轮循环，不用更新bitsptr, 以用到它后半部分的0位
    }
    //分配失败，没有足够的空间
    return NULL;
}

void FreeBitsBlock(bitmap* dstBitmap, uint32_t blockstart, uint32_t blocksize){
    ClearBits(dstBitmap, blockstart, blocksize);
    return ;
}
